import common.ListNode;

/**
 * 25. Reverse Nodes in k-Group K 个一组翻转链表
 * https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
 */
class ReverseKGroup {
    /**
     * 方法：反转链表中每k个节点的顺序
     * 
     * Args:
     *   head: 链表头节点
     *   k: 每k个节点反转一次
     * 
     * Returns:
     *   反转后的链表头节点
     * 
     * Time: O(N) - 需要遍历一次链表
     * 
     * Space: O(1) - 只使用常数额外空间
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1, head);
        ListNode prev = dummy;

        while(true){
            ListNode end = prev;
            //计算剩余节点是否满足k个
            for(int i = 0; i < k; i++){
                end = end.next;
                if(null == end){
                    return dummy.next;
                }
            }
            // 记录当前段的头和下一段的头
            ListNode start = prev.next;
            ListNode nextSeg = end.next;

            // 断开当前段，准备翻转
            end.next = null;
            prev.next = reverse(start);

            //重新连接翻转后的子链表
            start.next = nextSeg;
            // 跟新prev
            prev = start;
        }
    }

    private ListNode reverse(ListNode head){
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;

    }
}